During each unit of time, the particle moves its location either one
unit leftwards (with probability )
or one unit rightwards (with probability ).More specifically, if denotes the location of the
particle at time , then Therefore, where is the starting
position and are
independent random variables, each taking either the value −1 with
probability or the value with probability . We call the process a simple random
walk
It is called symmetric random walk if and
asymmetric random walk otherwise
Random walks are examples of so-called Markov
chains
Transition probabilities
Theorem 10.6 Let be the probability that a simple random walk revisits its
starting point at time . Then
if is odd, and if is even This is non-zero whenever is such that is an integer between
and . The result of Theorem 10.6 is
retrieved by setting .
Recurrence and
transience of random walks
If the walk is bound (with probability 1) to
revisit its starting point, we call it recurrent, and
otherwise we call it transient.
Theorem 10.12 The probability that a simple random walk ever
revisits its starting point is given by Hence the walk is recurrent if and only if
be
the (random) time until the first return. We have shown
that if
,In other words,
although a symmetric random walk is certain to return to its starting
point, the expected value of the time which elapses
before this happens is infinite.
The Gambler’s Ruin Problem
Theorem 10.23 (Gambler’s Ruin) Consider a simple
random walk on
with absorbing barriers at and
. If the walk begins at the point
, where , then the probability that the walk is absorbed at is given by
Theorem 10.28 (Recurrence/transience of random
walk) Consider a simple random walk on with absorbing
barriers at and . If the walk begins at the point , where , then the expected number of steps before the walk is absorbed
at either or is given by Thus, the expected number of flips of the
coin before either or becomes bankrupt in the Gambler’s Ruin
Problem is given by this formula.
Theorem 10.32 Consider a simple random walk on with an absorbing
barrier at . If the walk begins at
the point , the probability
that the walk is ultimately
absorbed at is given by
